package com.demo;

import javax.swing.*;
import java.util.Arrays;

public class DemoSort {

    public static void main(String[] args) {
        //int a[] = new int[]{2, 0, 1, 3, 5, 9, 6, 4, 7, 8};
        //bubbleSort(a);
        //quickSort(a, 0, a.length - 1);
        //selecttionSort(a);
        //insertionSort(a);
       // merge(a, 0, a.length - 1);
        //.out.println(Arrays.toString(a));

    }


    //1-冒泡排序
    public static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean b = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int tem = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tem;
                    b = true;
                }
            }
            if (!b) {
                System.out.println("没有数据交换了");
                break;
            }
        }
    }

    //2-快速排序
    public static void quickSort(int[] a, int left, int right) {
        if (left > right) {
            return;
        }
        int i = left;
        int j = right;
        int js = a[left];
        while (i < j) {
            while (js <= a[j] && i < j) {  //从右到左找比基数小的数
                j--;
            }
            while (js >= a[i] && i < j) {  //从左到右找比基数大的数
                i++;
            }
            if (i < j) {
                int tem = a[i];
                a[i] = a[j];
                a[j] = tem;
            }

        }
        a[left] = a[i];
        a[i] = js;
        quickSort(a, left, i - 1);//对左边子数组快速排序
        quickSort(a, i + 1, right);//对右边子数组快速排序
    }

    //3-选择排序
    public static void selecttionSort(int a[]) {
        for (int i = 0; i < a.length - 1; i++) {
            int k = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[k] > a[j]) {
                    k = j;
                }
            }
            if (i != k) {
                int tem = a[i];
                a[i] = a[k];
                a[k] = tem;
            }

        }
    }

    //4-插入排序
    public static void insertionSort(int a[]) {
        int j;
        for (int i = 1; i < a.length; i++) {
            int tem = a[i];
            for (j = i - 1; j >= 0 && a[j] > tem; j--) {
                a[j + 1] = a[j];
            }

            a[j + 1] = tem;

        }
    }

    //5-merge-归并排序
    //将两个子序列合并成一个
    public static void mergeSort(int a[], int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];//辅助数组
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = a[i++];  //将剩余的元素添加到辅助数组中
        }
        while (j <= right) {
            tmp[k++] = a[j++]; //同上
        }
        k = left;

        for (int t = 0; t < tmp.length; t++) {
            a[k++] = tmp[t];
        }

    }

    public static void merge(int a[], int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            merge(a, start, mid);
            merge(a, mid + 1, end);
            mergeSort(a, start, mid, end);
        }

    }
}
